\subsection{Übungsblatt 5 - Chinesischer Restsatz}
\subsubsection{Übung i}
Lösen Sie die simultane Kongruenz $x \equiv 0~mod~2$, $x \equiv 1~mod~3$, $x \equiv 2~mod~5$, $x \equiv 2~mod~7$ mit Hilfe des chinesischen Restsatzes.\\

Errechne m:
\[
m=\prod_{i=1}^{n}m_i=2*3*5*7=210
\]
Errechne $M_i$:
\[
M_i=m/m_i \quad M_1=\frac{210}{2}=105,~M_2=\frac{210}{3}=70,~M_3=\frac{210}{5}=42,~M_4=\frac{210}{7}=30 
\]
Löse:
\[
y_1*M_1 \equiv 1 \mod m_1 \Leftrightarrow y_1*105 \equiv 1 \mod 2 \Rightarrow y_1=1
\]
\[
y_2*M_2 \equiv 1 \mod m_2 \Leftrightarrow y_2*70 \equiv 1 \mod 3 \Rightarrow y_2=1
\]
\[
y_3*M_3 \equiv 1 \mod m_3 \Leftrightarrow y_3*42 \equiv 1 \mod 5 \Rightarrow y_3=3
\]
\[
y_4*M_4 \equiv 1 \mod m_4 \Leftrightarrow y_4*30 \equiv 1 \mod 7 \Rightarrow y_4=4
\]
Errechne $x$ mit:
\[
x=(\sum_{i=1}^{n}a_iy_iM_i) \mod m \Leftrightarrow x=0*1*105+1*1*70+2*3*42+2*4*30 \mod 210 \Leftrightarrow 70+252+240 \mod 210 \Rightarrow x = 142
\]
\subsubsection{Übung ii}
Die Nachricht $m$ wird mit dem öffentlichen RSA-Schlüsseln $(391,~3)$, $(55,~3)$, $(87,~3)$ verschlüsselt. Die Schlüsseltexte sind 208, 38 und 32. Verwenden Sie die Low-Exponent-Attacke, um $m$ zu finden.\\

Gegeben: $c_1=208,~c_2=38,~c_3=32,~n_1=391,~n_2=55,~n_3=87$

$c \equiv c_i \mod n_i$ für $1 \le i \le 3$ und $c = m^3$
d.h.
$c \equiv 208 \mod 391, c \equiv 38 \mod 55, c \equiv 32 \mod 87$

Gesucht ist eine ganze Zahl $c$ mit $0 \le c <  391*55*87$, die die simultane
Kongruenz erfüllt.

Löse:
\[
x_1*n_2*n_3 \equiv 1 \mod n_1 \Leftrightarrow x_1*4785 \equiv 1 \mod 391 \Rightarrow x_1=185
\]
\[
x_2*n_1*n_3 \equiv 1 \mod n_2 \Leftrightarrow x_2*34017 \equiv 1 \mod 55 \Rightarrow x_2=53
\]
\[
x_3*n_1*n_2 \equiv 1 \mod n_3 \Leftrightarrow x_3*21505 \equiv 1 \mod 87 \Rightarrow x_3=49
\]
Löse:
\[
c=(c_1x_1n_2n_3+c_2n_1x_2n_3+c_3n_1n_2x_3) \mod n_1n_2n_3=208*185*55*87+38*391*53*87+32*391*55*49 \mod 391*55*87 \]
\[
=184126800-2585292+33719840 \mod 391*55*87=215261348 \mod 1870935=103823 
\]
\[
\Rightarrow m=\sqrt[3]{103823}=47
\]
\subsubsection{Übung iii}
Sei $n = pq$ ein RSA-Modul und bezeichne $(\Z/p\Z) \times (\Z/q\Z)$ die Menge der Paare, deren Einträge aus $(\Z/p\Z)$ bzw. $(\Z/q\Z)$ stammen. Auf $(\Z/p\Z) \times (\Z/q\Z)$ wird eine Addition kompenentenweise definiert, d.h. $(a + p\Z, b + q\Z) \oplus (c + p\Z, d + q\Z) = ((a + c) + p\Z, (c + d) + q\Z)$. Für die Multiplikation verfährt man entsprechend.

Mit $\tau$ sei folgende Abbildung definiert: $\tau : (\Z/n\Z) \rightarrow (\Z/p\Z) \times (\Z/q\Z), x + n\Z \rightarrow (x + p\Z, x + q\Z)$.

Zeigen Sie, dass
\begin{itemize}
\item $\tau$ eine bijektive Abbildung ist
\item dass $\tau$ ein Homomorphismus der additiven Gruppen $(\Z/p\Z)$ und $(\Z/p\Z) \times (\Z/q\Z)$ sowie der multiplikativen Gruppen $(\Z/p\Z)^{*}$ und $(\Z/p\Z)^{*} \times (\Z/q\Z)^{*}$ ist.
\end{itemize}

\medskip
\textbf{Injektivität:}

$\tau(x + n\Z) = \tau(y + n\Z)
\text{ gdw. } (x+pZ,x+qZ)=(y+pZ,y+qZ)$

gdw. (komponentenweise Übereinstimmung):
$x + p\Z = y + p\Z \text{ und }
x + qZ = y + qZ$

gdw. 
$x \equiv y \mod p \text{ und }
x \equiv y \mod q$
gdw.
$p | (x-y) \text{ und } q | (x-y)$
gdw. (da $p$ und $q$ teilerfremd sind)
$pq | (x-y)$
gdw.
$x \equiv y \mod n$

d.h. die Funktionswerte unter der Abbildung $\tau$ stimmen genau dann
überein, wenn die Argumente in $\Z/n\Z$ gleich waren.

Da die Mengen $\Z/n\Z$ und $\Z/p\Z \times \Z/q\Z$ beide $n = pq$
Elemente haben, ist eine injektive Abbildung auch bijektiv.
\medskip\\

\textbf{Homomorphismus:}

Zu beweisen ist, dass $\tau(x + n\Z + y + n\Z) = \tau(x + n\Z) \oplus
\tau(y + n\Z)$ für beliebige $x + n\Z, y + n\Z  \in \Z/n\Z$ gilt.

Nach den Rechenregeln in $\Z/n\Z$ ist

$(x + n\Z) + (y+ n\Z) = (x+y) + n \Z$

Nach Definition von $\tau$ ist damit

$\tau((x + n\Z) + (y+ n\Z)) = \tau( (x+y) + n \Z ) =
( (x+y) + p\Z, (x+y) + q\Z)$

Dieser Ausdruck ist aufgrund der Rechenregeln in $\Z/p\Z$ und $\Z/q\Z$
gleich

$( (x+ p\Z) + (y + p\Z), (x+ q\Z) + (y + q\Z) )$.

Da in $\Z/p\Z \times \Z/q\Z$ die Addition $\oplus$ komponentenweise
definiert ist, entspricht dies

$( x+ p\Z, x+ q\Z) \oplus (y + p\Z, y + q\Z))$

Dies ist aber gerade

$\tau(x + n\Z) \oplus \tau(y + n\Z)$.
